A number of systems and programs are offered on the market for the design, the engineering and the manufacturing of objects. CAD is an acronym for Computer-Aided Design, e.g. it relates to software solutions for designing an object. CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM is an acronym for Computer-Aided Manufacturing, e.g. it relates to software solutions for defining manufacturing processes and operations. In such systems, the graphical user interface (GUI) plays an important role as regards the efficiency of the technique. These techniques may be embedded within Product Lifecycle Management (PLM) systems. PLM refers to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise.
The PLM solutions provided by Dassault Systemes (under the trademarks CATIA, ENOVIA and DELMIA) provide an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
Such systems allow defining surfaces representing modeled objects or parts of modeled objects in an interactive way for designers. A famous method frequently used in CAD systems is the boundary representation (B-Rep) model using parametric surfaces, including e.g. planes, quadrics such as cylinders, spheres, cones or even torus, procedural surfaces such as fillets, sweeps, or revolve surfaces, and/or non-uniform rational B-Spline surfaces (NURBS). Representing complex object with this technology may be performed via the widely known concept of trimmed surfaces. Trimmed surfaces allow designing any kind of surface and solid models. A trimmed surface is a parametric surface delimited by boundaries. A trimmed surface may typically be associated to a portion of the 2D domain of a respective parametric surface. For example, referring to FIG. 1, four surfaces 31-34 are trimmed resulting in four new delimited (or “trimmed”) respective surfaces 36-39.
In other words, some known CAD systems allow designers to interactively define a B-Rep of a modeled object, the boundary representation comprising geometrical data including parametric surfaces and topological data including a set of faces each defined as a portion of the 2D domain of a respective parametric surface.
Once (or while being) defined by designers, such surfaces often need to be rendered, e.g. in order to be displayed. Systems offering rendering functionality may indeed for example display surfaces e.g. during the modeling or for the purpose of review/modification by designers. Today, a computer's Graphic Processor Unit (GPU) can display thousands of triangles really efficiently. However, a GPU cannot display a surface provided as a B-Rep directly. Such surfaces must be transformed into a set of primitives that can be handled by the GPU. This is also the case for geometric operators (i.e. operators performing geometric or Boolean operations on several surfaces, e.g. for collision tests). Such transformation is called tessellation. Known tessellation methods approximate a surface by covering said surface with a pattern of flat polygons, usually triangles, with no gaps or overlaps, so as to fit as best as possible the mathematical definition of that surface, and sometimes by associating normal vectors to the pattern of flat polygons equal to corresponding surface normal vectors (i.e. vectors normal to the initial surface at corresponding positions) for the purpose of surface shading.
Thus, a surface of a modeled object can be processed via two different models. The first model is the exact model, which stands for the mathematical definition of surfaces. With the exact model, a user can design the surface and apply, on the surface, operators such as trim, bevel, or fillet operators. The second model is an approximated model, which is a geometric representation of the exact model usually used for visualization and geometric operations. Approximating smooth surfaces with flat geometry leads to discretization problems. This is a well-known problem in CAD applications. The smallest subset of triangles must be found to approximate surface curvature as best as possible. In order to determine if the approximation is acceptable in relation to the exact surface, an error bound tolerance is usually defined by the user.
Two approaches to tessellation exist nowadays.
The first approach is called “static” tessellation. Static tessellation comprises directly transforming a surface into a set of flat triangles approximating the surface. Vertices constituting such triangles are determined from the exact model of the surface, and sometimes normal vectors are also computed from the exact model and associated to the vertices or the triangles. Systems offering static tessellation functionalities usually provide the possibility to the user to define a maximum deviation or error value. The tessellation is then performed so that the distance from the triangles to the original surface does not exceed the error bound tolerance or deviation defined by the user. FIGS. 2 and 3 schematically illustrate deviation between a surface 20 and its approximation with triangles 22. The deviation is larger on FIG. 2 than on FIG. 3 (the deviation is here represented as chordal deviation on a circle), because FIG. 3 uses more triangles 22 to approximate surface 20. Generally, given a maximum deviation (i.e. a constraint that the deviation must be inferior to a certain value called “maximum deviation”) provided by the user, fewer triangles are needed in a flat area unlike in high curvature region where a higher density of triangles is needed to satisfy the given tolerance.
Static tessellation produces a heavy mesh with an average accuracy for vertices and normals and consumes huge memory for high curvature models, which is an issue when the approximate model is placed on persistent memory. Another issue with static tessellation appears when the accuracy needs to be increased. First of all, this is not always possible, because the exact model may have been previously discarded. Indeed, the exact model usually consumes a lot of memory space and may either be deleted, or discarded when the designer wants to send the modeled object elsewhere, e.g. for displaying and/or for geometric operations, e.g. to another user and/or another client system. With static tessellation and in such a case, only the approximated model consisting of the set of flat triangles respecting a maximum deviation pre-provided by the user is kept or sent, and a higher accuracy can never be reached (the exact information being lost). Second of all, in cases that the exact model is nevertheless kept, an issue is that, when demanding a higher accuracy, the tessellation has to be performed from scratch, i.e. from the exact model of the surface. This takes a lot of time.
In order to alleviate these issues, another approach to tessellation called “PNT tessellation” has been developed. The idea behind PNT tessellation is to use a multi-resolution model called “PNT”. More precisely, the idea behind PNT tessellation is to parameterize a three-dimensional modeled object for tessellation, i.e. prepare the object for tessellation, so that less time is needed when the tessellation needs to be performed. As a result, re-doing the tessellation e.g. in order to increase the accuracy of the approximated model is less time-consuming than in the case of static tessellation (in the case when the exact model is available).
Specifically, PNT tessellation produces a piecewise approximation of a surface with a set of triangular patches (possibly non-flat). This results in a lightweight intermediate model representation called the “base mesh”. FIG. 4 shows an example of a base mesh 40, with triangular patches 42, in bold, that are not (necessarily) flat, tessellated with smaller flat triangles 44. These triangular patches 42 approximate the exact surface e.g. using a cubic Bezier formulation. PNT tessellation is a good trade off in terms of memory and computation. Instead of keeping exact surfaces, this lightweight model is the entry point for visualization, and/or geometric operators. As it is a lightweight coarse approximation, a pre-compute, i.e. parameterization, step is needed where triangular patches are used to fit the surface definition for any kind of purpose. Then, in order to perform the actual tessellation starting from the model parameterized for the tessellation (i.e. the base mesh), each patch may be refined following a subdivision pattern (simpler and faster than the tessellation from scratch). The subdivision may be made on demand according to any required chordal deviation, in order to add more triangles where they are needed. These refined triangles are evaluated from the previous triangle formulation. The PNT approach thus allows to increase accuracy on demand even if the exact model is discarded (but under the condition that the base mesh is kept), in a relatively fast way. Also, the memory consumption is improved, as the base mesh generally consumes less memory space than the tessellated model.
However, PNT tessellation also presents issues. For example, the possibility to increase accuracy (without using the initial exact model, which may have been discarded) still has a limit, because the base mesh is only an approximation of the initial surface. Furthermore, the base mesh approximates the surface in terms of positions, but computing normal vectors from the base mesh may prove relatively inaccurate. As a cubic Bézier is used for vertices computation, normals are computed with a linear or quadratic interpolation. As a result, visualization artifacts happen while rendering the final mesh. For instance, surface representation and shading are deteriorated.
The above information is discussed in a number of papers, of which a list is provided below:                P. Bezier. Definition numerique des courbes et surfaces I. Automatisme, XI:625-632, 1966;        P. Bezier. Mathematical and practical possibilities of UNISURF. In R. Barnhill and R. Riesenfeld, editors, Computer Aided Geometric Design, pages 127-152. Academic Press, 1974;        C. de Boor A Practical Guide to Splines, Springer, 1978;        P. de Casteljau Courbes et surfaces à pôles. Technical report, A. Citroen, Paris, 1963;        P. de Casteljau. Le Lissage. Hermes, Paris, 1990;        G. Farin. Curves and Surfaces for CAGD: A Practical Guide, Fifth Edition. Academic Press, San Diego, 2002        Vlachos, J. Peters, C. Boyd, and J. L. Mitchell. Curved PN triangles. In Symposium;        on Interactive 3D Graphics, pages 159-166, 2001;        Guthe M., Balázs Á., and R. Klein, GPU-based Trimming and Tesselation of NURBS and T-Spline; and        Surfaces, ACM SIGGRAPH conference proceedings, 2005.        
The existing solutions mentioned above thus lack efficiency. Within this context, there is still a need for an improved solution for the tessellation of a 3D modeled object.